package leetcode.array;

/**
 * @author wangmaolin1
 * @date 2022/1/5 下午11:23
 */
public class _88合并两个有序数组 {

    /**
     * nums1.length=m+n num2合并到 nums1中
     *
     * @param nums1 非递减
     * @param m     nums1元素数目
     * @param nums2 非递减
     * @param n     nums2元素数目
     */
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int[] temp = new int[nums1.length];
        int l1 = 0, l2 = 0;
        int i = -1;
        while (l1 < m && l2 < n) {
            if (nums2[l2] < nums1[l1]) {
                temp[++i] = nums2[l2];
                l2++;
            } else {
                temp[++i] = nums1[l1];
                l1++;
            }
        }
        while (l1 < m) {
            temp[++i] = nums1[l1];
            l1++;
        }
        while (l2 < n) {
            temp[++i] = nums2[l2];
            l2++;
        }
        System.arraycopy(temp, 0, nums1, 0, nums1.length);
    }

    /**
     * 从尾部开始的双指针 不需要额外空间
     *
     * @param nums1
     * @param m
     * @param nums2
     * @param n
     */
    public void mergeFromTail(int[] nums1, int m, int[] nums2, int n) {
        int l1 = m - 1, l2 = n - 1;
        int tail = m + n - 1;
        while (l1 >= 0 || l2 >= 0) {
            int cur;
            if (l1 == -1) {
                cur = nums2[l2--];
            } else if (l2 == -1) {
                cur = nums1[l1--];
            } else if (nums1[l1] > nums2[l2]) {
                cur = nums1[l1--];
            } else {
                cur = nums2[l2--];
            }
            nums1[tail--] = cur;
        }
    }


}
